#include <cstdio>

int main( )
{
    __int64 a, b, n, m, cas = 1, i, cnt, p;
    while ( scanf("%I64d%I64d", &a, &b) != EOF )
    {
        n = 1;
        i = 2;
        while ( i * i <= a )
        {
            cnt = 0;
            while ( a % i == 0 )
            {
                a /= i;
                cnt++;
                
            }
            p = ( cnt * b + 1 ) * ( cnt * b + 2 ) / 2 % 10007;
            n = ( n * ( ( p * p ) % 10007 ) ) % 10007;
            i++;
        }
        if ( a != 1 )
        {
            p = ( b + 1 ) * ( b + 2 ) / 2 % 10007;
            n = ( n * ( ( p * p ) % 10007 ) ) % 10007;
        }
        printf("Case %I64d: %I64d\n", cas++, n);
    }
    return 0;
}
